#
# @lc app=leetcode.cn id=148 lang=python3
#
# [148] 排序链表
#

# @lc code=start
# Definition for singly-linked list.
from typing import List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        # return self.quickSort(head)
        length = 0
        end = head
        while end:
            length += 1
            end = end.next

        merge_len = 1
        start = ListNode(next=head)
        while merge_len < length:
            end = start
            cur = start.next
            while cur:
                head1 = cur
                for _ in range(merge_len - 1):
                    if not cur.next:
                        break
                    cur = cur.next

                if not cur.next:
                    end.next = head1
                    break

                head2 = cur.next
                cur.next = None
                cur = head2
                for _ in range(merge_len - 1):
                    if not cur.next:
                        break
                    cur = cur.next
                tmp = cur
                cur = cur.next
                tmp.next = None

                sub_start, sub_end = self.merge(head1, head2)
                end.next = sub_start
                end = sub_end
            merge_len *= 2
        return start.next

    def quickSort(self,
                  head: ListNode,
                  head_l: ListNode = None,
                  end: ListNode = None) -> ListNode:
        if head is end:
            return head

        bigger = cur = head.next
        bigger_l = cur_l = head
        bigger_l2 = head_l = head_l if head_l else ListNode(next=head)
        while cur is not end:
            if cur.val < head.val:
                bigger_l2 = bigger_l
                cur_l.next, bigger_l.next = bigger, cur
                cur_l, bigger_l = bigger, cur
                cur.next, bigger.next = bigger.next, cur.next
                cur, bigger = bigger.next, cur.next
            else:
                cur_l = cur
                cur = cur.next
        bigger_l2.next, head_l.next = head, bigger_l
        head.next, bigger_l.next = bigger, head.next
        head, bigger_l = bigger_l, head

        head = self.quickSort(head, head_l, bigger_l)
        self.quickSort(bigger, bigger_l, end)

        return head

    def merge(self, head1: ListNode, head2: ListNode) -> ListNode:
        ret = cur = ListNode()
        while head1 and head2:
            if head1.val <= head2.val:
                cur.next = head1
                head1 = head1.next
            else:
                cur.next = head2
                head2 = head2.next
            cur = cur.next

        head = head1 or head2
        while head:
            cur.next = head
            cur = cur.next
            head = head.next

        return ret.next, cur


# @lc code=end
def node2list(head: ListNode) -> List:
    ret = []
    while head is not None:
        ret.append(head.val)
        head = head.next
    return ret


def list2Node(lst: List) -> ListNode:
    head = node = ListNode()
    for i in lst:
        node.next = ListNode(i)
        node = node.next
    return head.next


if __name__ == "__main__":
    s = Solution()
    lst1 = [4, 2, 1, 3]
    head1 = s.sortList(list2Node(lst1))
    print(node2list(head1))

    lst2 = [-1, 5, 3, 4, 0]
    head2 = s.sortList(list2Node(lst2))
    print(node2list(head2))

    lst3 = []
    head3 = s.sortList(list2Node(lst3))
    print(node2list(head3))
